package sparse

// 稀疏图 - 领接表
type Graph struct {
	n int // 点数
	m int // 边数
	directed bool // 有向图 无向图
	vector [][]int
}

func newGraph(n int, directed bool) {
	graph := new(Graph)
	graph.n = n
	graph.m = 0
	graph.directed = directed

	for i := 0; i < n; i++  {
		graph.vector[i] = make([]int, 0)
	}
}

// 顶点
func (dg *Graph) V() int {
	return dg.n
}

// 边
func (dg *Graph) E() int {
	return dg.m
}

func (dg *Graph) addEdge(v int, w int)  {

	if dg.hasEdge(v, w) {
		return
	}

	dg.vector[v] = append(dg.vector[v], w)
	if v != w && !dg.directed {
		dg.vector[w] = append(dg.vector[w], v)
	}
	dg.m++
}

func (dg *Graph) hasEdge(v int, w int) bool {
	for i := 0; i < len(dg.vector[v]); i++ {
		if dg.vector[v][i] == w {
			return true
		}
	}

	return false
}